#include<vector>
#include<algorithm>
using namespace std;
class Solution {
public:
    int largest1BorderedSquare(vector<vector<int>>& grid) {
        vector<vector<int>>dp(grid.size() + 1);
        for (int i = 0; i < dp.size(); ++i)
            dp[i].resize(grid[0].size() + 1);
        for (int i = 1; i <= grid.size(); ++i) {
            for (int j = 1; j <= grid[i - 1].size(); ++j) {
                if (grid[i - 1][j - 1] == 1)
                    dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + 1;
                else
                    dp[i][j] = 0;
            }
        }
        vector<int>dp0(grid[0].size() + 1);
        vector<int>dp1(grid[0].size() + 1);
        int res = 0;
        for (int i = grid.size() - 1; i >= 0; --i) {
            for (int j = grid[i].size() - 1; j >= 0; --j) {
                if (grid[i][j] == 1)
                    dp1[j] = min(dp1[j + 1], dp0[j]) + 1;
                else
                    dp1[j] = 0;
                for (int k = dp1[j]; k > 0; --k) {
                    if (dp[i + k][j + k] >= k) {
                        res = max(res, k);
                        break;
                    }
                }
            }
            swap(dp0, dp1);
        }
        return res * res;
    }
};

int main() {
    vector<vector<int>> matrix = { {1,1,1} ,{1,0,1},{1,1,1} };
    Solution sol;
    sol.largest1BorderedSquare(matrix);
}